//https://leetcode.cn/problems/uOAnQW/description/?envType=daily-question&envId=2024-08-01


class Solution {
public:
    int maxmiumScore(vector<int>& cards, int cnt) {
        ranges::sort(cards, greater());
        int s = reduce(cards.begin(), cards.begin() + cnt, 0); // 最大的 cnt 个数之和
        if (s % 2 == 0) { // s 是偶数
            return s;
        }

        auto replace_sum = [&](int x) -> int {
            for (int i = cnt; i < cards.size(); i++) {
                if (cards[i] % 2 != x % 2) { // 找到一个最大的奇偶性和 x 不同的数
                    return s - x + cards[i]; // 用 cards[i] 替换 s
                }
            }
            return 0;
        };

        int x = cards[cnt - 1];
        int ans = replace_sum(x); // 替换 x
        for (int i = cnt - 2; i >= 0; i--) { // 前 cnt-1 个数
            if (cards[i] % 2 != x % 2) { // 找到一个最小的奇偶性和 x 不同的数
                ans = max(ans, replace_sum(cards[i])); // 替换
                break;
            }
        }
        return ans;
    }
};

